By

文章目录
  1. 1. 题目
  2. 2. 思路
    1. 2.1. 简化
    2. 2.2. 还原
  3. 3. 代码
  4. 4. 推广
    1. 4.1. p%k!=0

本系列代码见我的Leetcode仓库

题目

Given an array of integers, every element appears three times except for one. Find that single one.

题目描述是leetcode的Single Number II问题，在一个数组中所有的数都出现了3次，除了其中某一个（那么这个数出现多少次呢？题目并没有说明，但从结果上来看它默认为这个Single Number只出现了一次)。题目本身难度不大，但他的推广非常有趣，所以激起了我写上博客的兴趣。

思路

这个题我一开始有两个思路，一个是像Single Number那个题一样，采用位操作，另外一个是像讨论区有个人的解法一样，把所有数做成集合，利用Python便捷的计算工具计算出和，再得到那个出现次数不一样的数，有点作弊的意思。
重点分析第一种思路。其实要解这个题最根本的在于如何记录每个数字出现的次数，如果有一种方法可以把每个出现过的数字的次数记下来，这个题自然就解决了。直接统计次数涉及到O(n)的空间和O(n)的时间，而且这些空间是不必要的，考虑用位操作来记录。

简化

首先考虑简化版即Single Number那个问题的情况，其他数字都出现两次。那么我们可以想到，如果新的数字已经出现过了，就可以把记录中对应的内容“冲掉”，这样这个数字就被排除在外了。那么什么方式可以把已经出现的数字冲掉呢？嗯，就是异或。

好，这是相同数字连续出现的情况，如果不连续呢？我们来分析一下。任何32位的数字都可以表示成01串，也就是说，任何一个数字如果出现了两次，那么它的每一位上的0或1都出现了两次，那么所有出现过两次的数字全部异或起来，其结果一定是全0，跟数字出现的顺序无关。而妙的是，如果一个数字只出现了1次，那它跟全0的异或结果，就是它本身。

现在我们发现，如果只出现一次的那个数字在最开始或最后，就可以通过全异或来得到它了。那么它的位置有没有影响呢？结论是没有。试想，这个数字出现在任意一个位置，异或操作将它的1的位都标记了一次，而它之前或之后的数字，由于都出现了两次，所以对整个串的影响将会被异或消除掉，也就是说最后剩下来的一定是这个没有被“冲掉”的数字。至此，简化版问题就解决了。

状态 当前number出现次数
0 0
1 1
0 2

（以上应该是个表格）

还原

现在来考虑简化版背后的故事。为什么是全元素异或？因为所有元素都出现两次，除了要找的那个元素，异或操作可以让任意一个出现第二次的数对结果的影响消失，就像他没出现过一样。仔细想想，这其实就是两种状态，即出现一次的状态和出现两次（消失）的状态，所以我们用一位就可以表示。0是未出现或出现两次，1是出现一次，那么Single Number就会使状态为1。这里的0和1只是代指，实际上是一个32位整型变量，0是全0，1是出现过1次的number的值（事实上，在每一步时并不是这样，只有当所有相同的数都挨在一起时才是，但这并不影响）。

好，现在我们知道了，之所以可以用一次异或解决简化版问题，是因为简化版问题中只有两种状态。现在我们面临三种状态，即出现次数分别为0（3）、1、2次，要找到那个出现次数为1的数，应该怎么办？

有了前面的铺垫，自然而然我们就想到是不是有一种方式可以表示三种状态，且其中某一种状态正好就存储了我们需要的数？说到状态，又是位操作，我们很容易就想到，00、01、10不就可以表示三种状态吗？正好对应某个数出现0（3）、1、2次的情况，而且01还可以存储出现1次的那个数，简直太完美了！

现在解决方案找到了，但这三个状态怎么写，怎么存呢？当然你可以直接用两个变量，像简化版那样，只不过当异或的结果为0时用另一个变量存储这个数，作为10这个单独的状态。但这里实际上有个小技巧：观察一下00->01->10->00，始终记住1表示我们当前遇到的数。我们用b1b0表示这两个位。最初b1b0=00,当一个新的数来临时，我们发现它出现了第一次，于是b1b0=01，然后假设它出现了第二次，这时b1b0=10，然后是第三次，b1b0=00。有没有发现，当它出现第一次时是b0记录，第二次时是b1记录，第三次则冲掉了全部？根据之前的铺垫我们可以想到， 

b0=(b0^num)
b1=(b1^num)&(~b0)

直觉上这样好像哪里不对。确实，我们在数字出现第一次时记录到了b0，此时b1=0，到第二次时b0=0，b1=1，但第三次出现就不行了，因为此时b0又以为他是第一次出现，b0=1.究其原因是它不知道b1已经记录过这个数字的第二次出现。所以b0需要在这个数字没有出现第二次时(b1==0)记录它，作为第一次出现，而在它已经出现第二次时(b1==1)记录为0，作为第三次出现。根据这个思路，改进一下：

b0=(b0^num)&(~b1)
b1=(b1^num)&(~b0)

最后，只出现一次的数字一定会停留在b1b0=01的状态，这时b0就是该数字。

|状态|当前number出现次数|
|00|0|
|01|1|
|10|2|
|00|3|

代码

1
2
3
4
5
6
7
8
9
class Solution:
    # @ param {integer[]} nums
    # @ return {integer}
    def singleNumber(self, nums):
        b0=b1=0
        for num in nums:
            b0=(b0^num)&(~b1)
            b1=(b1^num)&(~b0)
        return b0

推广

前面说过，这个题的推广非常有趣，在讨论区中有人提出对推广问题的思考。试想一下，如果我们数组中，所有其它数字出现的次数是k次，除了某一个数字出现次数是p（p!=k）次，请问如何找到这个数字？
根据我之前的思路，很显然如果我们能找到足够多的位，可以表示k个状态，那么第p%k个状态就是我们要找的数字了，这里为简单起见，先假设p%k!=0，然后再推广到p%k==0的情况。

p%k!=0

我们需要多少位来表示k个状态呢？显然是2^m>=k -> m>=logk
于是接下来的问题就变成了，每出现一个数，状态就转移一次，注意到上面的状态转移，其实就是一个counter，对出现的数进行计数。现在可以分解为两个问题：

  1. 状态转移的时候，每一位怎么变化？以及
  2. 当状态到达k的时候，我们如何知道，从而将状态恢复到0？

状态转移的变化是很容易得到的：这就是一个counter=counter+1的过程，不同的是我们得用位操作来模拟，而且这里的1代表当前数字。假设我们当前状态是S=Sk-1,Sk-2,…S0=00…000，新来一个数，我们发现S0是0，于是把S0变为1，再来一个数，我们发现S0是1，S1是0，于是S1S0变为10，过程如下：

|状态|当前number出现次数|
|…000|0|
|…001|1|
|…010|2|
|…011|3|
|…100|4|
|…101|5|
|…110|6|
发现没有，任意一位Si要从0变为1的条件是，所有满足j<i的Sj==1，否则Si就不变化（其实就是2进制进位规则），即Si=Si^(Si-1&Si-2&…&S0&number)，对于S0，S0=S0^number
于是有： 

1
2
3
4
5
6
7
8
#注意顺序不可变，先确定高位是否改变再确定低位
Sm ^= (Sm-1 & ... & S1 & i)

Sm-1 ^= (Sm-2 & ... & S1 & i)

.....

S1 ^= i
文章目录
  1. 1. 题目
  2. 2. 思路
    1. 2.1. 简化
    2. 2.2. 还原
  3. 3. 代码
  4. 4. 推广
    1. 4.1. p%k!=0